package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/combination-sum-iii/">组合总和 III(Combination Sum III)</a>
 * <p>
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 *     <ul>
 *         <li>只使用数字1到9</li>
 *         <li>每个数字 最多使用一次 </li>
 *     </ul>
 *     返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: k = 3, n = 7
 *      输出: [[1,2,4]]
 *      解释:
 *          1 + 2 + 4 = 7
 *          没有其他符合的组合了。
 *
 * 示例 2:
 *      输入: k = 3, n = 9
 *      输出: [[1,2,6], [1,3,5], [2,3,4]]
 *      解释:
 *          1 + 2 + 6 = 9
 *          1 + 3 + 5 = 9
 *          2 + 3 + 4 = 9
 *          没有其他符合的组合了。
 *
 * 示例 3:
 *      输入: k = 4, n = 1
 *      输出: []
 *      解释: 不存在有效的组合。
 *          在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>2 <= k <= 9</li>
 *      <li>1 <= n <= 60</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @see LC0039CombinationSum_M
 * @see LC0040CombinationSum_II_M
 * @see LC0216CombinationSum_III_M
 * @see LC0377CombinationSum_IV_M
 * @since 2024/4/25 17:16
 */
public class LC0216CombinationSum_III_M {
    static class Solution {
        public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> resultList = new ArrayList<>();
            int[] c = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
            search(c, 0, k, n, new LinkedList<>(), resultList);
            return resultList;
        }

        private void search(int[] c, int startPoint, int k, int target, Deque<Integer> path, List<List<Integer>> resultList) {
            if (k == 0 && target == 0) {
                resultList.add(new ArrayList<>(path));
            }
            if (k == 0) {
                return;
            }
            for (int i = startPoint; i < 9; i++) {
                if (c[i] > target) {
                    return;
                }
                path.addLast(c[i]);
                search(c, i + 1, k - 1, target - c[i], path, resultList);
                path.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.combinationSum3(3, 7));
        Printer.printListListInteger(solution.combinationSum3(3, 9));
        Printer.printListListInteger(solution.combinationSum3(4, 1));
    }
}
